/**
 * Package:cn.tst.test;
 * $Id: AStar.java,v 1.3 2008/12/02 03:01:26 yangc Exp $
 * Copyright(c) 2001-2005 www.afteryuan.com
 */
package com.afteryuan.server.support.astar;

import com.afteryuan.server.support.Point;

import java.util.Vector;

/**
 * AStar
 * <p/>
 * <p><a href="AStar.java.html"><i>View Source</i></a></p>
 *
 * @author <a href="mailto:afteryuan@afteryuan.com">$Author: yangc $</a>
 * @version $Revision: 1.3 $
 */
public class AStar {
	//地图数组
	int[][] grid=null;
	//路径寻找的开始位置
	Point start=null;
	//路径寻找的目的位置
	Point goal=null;
	//开启节点列表
	NodeList open=null;
	//关闭节点列表
	NodeList closed=null;
	//预估耗费用的常量
	int[] cost=null;
	//直线单元耗费值
	public static final int linealCost=14;
	//对角线单元耗费值
	public static final int diagonalCost=10;
	//左上
	final int LEFT_TOP=1;
	//左下
	final int LEFT_BOTTOM=4;
	//右上
	final int RIGHT_TOP=6;
	//右下
	final int RIGHT_BOTTOM=8;

	public AStar(int[][] grid,int[] cost,Point start,Point goal){
		this.grid=grid;
		this.start=start;
		this.goal=goal;
		open=new NodeList();
		closed=new NodeList();
		this.cost=cost;
	}

	/**
	 * 释放节点，从起点到指定节点的所有节点
	 * @param node 指定节点
	 * @return 从起点到指定节点的所有节点的集合
	 */
	private Vector solve(Node node) {
        Vector solution = new Vector();

        solution.addElement(node);
        while(node.parent != null) {
            solution.insertElementAt(node.parent, 0);
            node = node.parent;
        }

        return solution;
    }

	/**
	 * 进行路径查找
	 * @return 返回路径集合
	 */
	public Vector find(){
		long startTime=System.currentTimeMillis();
		//为起点赋初值
		Node startNode=new Node();
		startNode.location=start;
		startNode.costFromStart=0;//g
		startNode.costToGoal=currnetToGoalCostEstimate(start,goal);//h
		startNode.totalCost=startNode.costToGoal+startNode.costFromStart;//f
		startNode.parent=null;

		open.addNode(startNode);

		while(open.size()>0){
			//寻找开启列表中F值最低的格子。我们称它为当前格
			Node currentNode=open.pop();
//			System.out.println("寻找开启列表中F值最低的格子:"+currentNode);

			//把目标格添加进了开启列表，这时候路径被找到
			if (currentNode.location.equals(goal)){
//				System.out.println("路径被找到");
//				System.out.println("共耗时:"+(System.currentTimeMillis()-startTime)+"ms");
				return solve(currentNode);
			}
			else{
				//把当前格切换到关闭列表
				closed.addNode(currentNode);
				//获得当前附近的节点集合
				Vector neighborList=getNeighbors(currentNode);

				boolean inOpenList=false;
				boolean inClosedList=false;

				for(int i=0;i<neighborList.size();i++){
//					System.out.println("开启列表内容:\n"+open);
					//计算邻居节点的耗费值
					Node neighborNode=(Node)neighborList.elementAt(i);

//					System.out.println("比较邻居节点:"+neighborNode);

					inOpenList=open.contains(neighborNode);
					inClosedList=closed.contains(neighborNode);

//					System.out.println("is in Open="+inOpenList);
//					System.out.println("is in Closed="+inClosedList);
					//如果它不可通过或者已经在关闭列表中，略过它
					if (inClosedList){
//						System.out.println("邻居节点已经在关闭列表!");
						continue;
					}
					//如果它不在开启列表中，把它添加进去。把当前格作为这一格的父节点。记录这一格的F,G,和H值。
					else{
						if (!inOpenList){
//							System.out.println("记录这一格的F,G,和H值");
							neighborNode.costFromStart=currentNode.costFromStart
								+neighborToCurrentCostEstimate(currentNode,neighborNode);
							neighborNode.costToGoal=currnetToGoalCostEstimate(neighborNode.location,goal);
							neighborNode.totalCost=neighborNode.costFromStart+neighborNode.costToGoal;
							neighborNode.parent=currentNode;
//							System.out.println("把它添加进开启表:"+neighborNode);
							open.addNode(neighborNode);
//							System.out.println("邻居节点不在开启列表中，被添加:\n"+neighborNode);
						}
						//如果它已经在开启列表中，用G值为参考检查新的路径是否更好。更低的G值意味着更好的路径。
						//如果是这样，就把这一格的父节点改成当前格，并且重新计算这一格的G和F值。
						//如果你保持你的开启列表按F值排序，改变之后你可能需要重新对开启列表排序。
						else{
							if ((currentNode.costFromStart+neighborToCurrentCostEstimate(currentNode,neighborNode))
									<currentNode.costFromStart){
//								System.out.println("邻居节点是G值低的\n"+neighborNode);
								currentNode=neighborNode.parent;
								neighborNode.costToGoal=currnetToGoalCostEstimate(neighborNode.location,goal);
								neighborNode.totalCost=neighborNode.costFromStart+neighborNode.costToGoal;
								open.sort();
//								System.out.println("重新对开启列表排序:\n"+open);
							}

						}


					}
				}
			}
		}
//		System.out.println("路径没有被找到");
//		System.out.println("共耗时:"+(System.currentTimeMillis()-startTime)+"ms");
		return null;
	}

	/**
	 * 计算从start到goal的矩形区域中平均耗费值
	 * @param start 起始位置
	 * @param goal 目标位置
	 * @return 从start到goal的矩形区域中平均耗费值
	 */
//	private double getAverageCost(Location start,Location goal){
//		int left=Math.min(start.x,goal.x);
//		int top=Math.min(start.y,goal.y);
//		int right=Math.max(start.x,goal.x);
//		int bottom=Math.max(start.y,goal.y);
//		double totalValue=0;
//		double count=0;
//		for(int i=left;i<=right;i++){
//			for(int j=top;j<=bottom;j++){
//				if (grid[i][j]!=Constants.NOTHING){
//					totalValue+=cost[grid[i][j]];
//					count++;
//				}
//			}
//		}
//		return totalValue/count/1.1;
//	}

	/**
	 * 计算从某节点到目标节点的预估耗费
	 * @param start 计算的起始点
	 * @param goal 计算的终点
	 * @return 返回从某节点到目标节点的预估耗费
	 */
	private int currnetToGoalCostEstimate(Point start,Point goal){
		int dx=Math.abs(start.x-goal.x);
		int dy=Math.abs(start.y-goal.y);
		return (dx+dy)*linealCost;
	}

	/**
	 * 计算从当前节点到其周围的邻居节点的预估耗费
	 * @param currentNode 当前节点
	 * @param neighborNode 邻居节点
	 * @return 从当前节点到其周围的邻居节点的预估耗费
	 */
	private int neighborToCurrentCostEstimate(Node currentNode,Node neighborNode){
		int dx=Math.abs(currentNode.location.x-neighborNode.location.x);
		int dy=Math.abs(currentNode.location.y-neighborNode.location.y);
		//如果为对角线方向
		if (dx==1&&dy==1){
            int index;
            //G=(x轴距离+y轴距离)*对角线单位耗费+当前节点的耗费
            if(grid[neighborNode.location.y][neighborNode.location.x] > Constants.SOLID){
                index = 0;
            }else{
                index = 1;
            }
            return (dx+dy)*diagonalCost+cost[index];
		}
		//如果为直线方向
		else{
            int index;
            if(grid[neighborNode.location.y][neighborNode.location.x] > Constants.SOLID){
                index = 0;
            }else{
                index = 1;
            }
            //G=(x轴距离+y轴距离)*直线单位耗费+当前节点的耗费
			return (dx+dy)*linealCost+cost[index];
		}//+cost[grid[neighborNode.location.x][neighborNode.location.y]];
	}

	/**
	 * 边界检测
	 * @param x x轴坐标
	 * @param y y轴坐标
	 * @return 如果出边界，则返回true
	 */
	private boolean isOutOfBorder(int x,int y){
		//测试边界
		if (y<0||y>=grid.length){
			return true;
		}
		//测试边界
		if (x<0||x>=grid[0].length){
			return true;
		}
		return false;
	}

	/**
	 * 条件性的增加节点
	 * @param neighborList 邻居列表
	 * @param location 当前节点的坐标
	 * @param dx x轴坐标增量
	 * @param dy y轴坐标增量
	 */
	private void conditionalAdd(Vector neighborList,Point location,int dx,int dy){
		int x=location.x;
		int y=location.y;
		int newX=x+dx;
		int newY=y+dy;

//		System.out.println("尝试增加邻近节点:x="+newX+" y="+newY);
		//测试边界
		if (isOutOfBorder(newX,newY)){
			return;
		}

		//跳过不能通过的物体
		if (grid[newY][newX]==Constants.SOLID){
			return;
		}

		//判断左上角邻居节点
		if ((dx==-1)&&(dy==-1)){
			if (isSkiped(LEFT_TOP,newX,newY)){
//				System.out.println("跳过节点"+location+"的左上角邻居节点");
				return;
			}
		}

		//判断左下角邻居节点
		if ((dx==-1)&&(dy==1)){
			if (isSkiped(LEFT_BOTTOM,newX,newY)){
//				System.out.println("跳过节点"+location+"的左下角邻居节点");
				return;
			}
		}

		//判断右上角邻居节点
		if ((dx==1)&&(dy==-1)){
			if (isSkiped(RIGHT_TOP,newX,newY)){
//				System.out.println("跳过节点"+location+"的右上角邻居节点");
				return;
			}
		}

		//判断右下角邻居节点
		if ((dx==1)&&(dy==1)){
			if (isSkiped(RIGHT_BOTTOM,newX,newY)){
//				System.out.println("跳过节点"+location+"的右下角邻居节点");
				return;
			}
		}

		Node neighbor=new Node();
		neighbor.location=new Point(newX,newY);
		neighborList.addElement(neighbor);
	}

	/**
	 * 判断处于拐弯处（左上、右上、左下、右下）的邻居节点，是否邻着不可穿透的固体，如果是则该节点被跳过
	 * @param direction 表示邻居节点与当前节点位置关系的左上、右上、左下、右下方向常量
	 * @param x 邻居节点的x坐标
	 * @param y 邻居节点的y坐标
	 * @return 判断处于拐弯处（左上、右上、左下、右下）的邻居节点，是否邻着不可穿透的固体，如果是则返回true
	 */
	private boolean isSkiped(int direction,int x,int y){
		int x1=0,y1=0;
		int x2=0,y2=0;

		switch(direction){
			//如果当前位置为左上角，则判断其下方和右侧是否为不可穿过的固体
			case LEFT_TOP:
				x1=x;
				y1=y+1;
				x2=x+1;
				y2=y;
				break;
			//如果当前位置为右上角，则判断其下方和左侧是否为不可穿过的固体
			case RIGHT_TOP:
				x1=x;
				y1=y+1;
				x2=x-1;
				y2=y;
				break;
			//如果当前位置为左下角，则判断其上方和右侧是否为不可穿过的固体
			case LEFT_BOTTOM:
				x1=x;
				y1=y-1;
				x2=x+1;
				y2=y;
				break;
			//如果当前位置为右下角，则判断其上方和左侧是否为不可穿过的固体
			case RIGHT_BOTTOM:
				x1=x;
				y1=y-1;
				x2=x-1;
				y2=y;
				break;
		}

		//根据计算后获得的坐标(x1,y1),(x2,y2)，判断其是否为不可穿越的物体
		//如果是，则跳过该邻居节点
		boolean result=false;
		//首先判断是否出边界
		if ((isOutOfBorder(x1,y1)==false)&&(isOutOfBorder(x2,y2)==false)){
			//然后判断是否为不可穿越的物体
			if ((grid[y1][x1]==Constants.SOLID)||(grid[y2][x2]==Constants.SOLID)){
				result=true;
			}
			else{
				result=false;
			}
		}
		return result;


	}

	/**
	 * 获得当前节点周围的邻居节点集合
	 * @param currentNode 当前节点
	 * @return 当前节点周围的邻居节点集合
	 */
	private Vector getNeighbors(Node currentNode){
		Vector neighborList=new Vector();

		//增加左上角邻居节点
		conditionalAdd(neighborList,currentNode.location,-1,-1);

		//增加左侧邻居节点
		conditionalAdd(neighborList,currentNode.location,-1,0);

		//增加左下角的邻居节点
		conditionalAdd(neighborList,currentNode.location,-1,1);

		//增加上方邻居节点
		conditionalAdd(neighborList,currentNode.location,0,-1);

		//增加下方邻居节点
		conditionalAdd(neighborList,currentNode.location,0,1);

		//增加右上角邻居节点
		conditionalAdd(neighborList,currentNode.location,1,-1);

		//增加右侧邻居节点
		conditionalAdd(neighborList,currentNode.location,1,0);

		//增加右下角邻居节点
		conditionalAdd(neighborList,currentNode.location,1,1);

		return neighborList;

	}
}
